10037. Мост

 

n людей ночью хотят перейти на другой берег реки по мосту. У них есть один фонарь. Двигаться по мосту с фонарем могут не более двух человек. Движение по мосту без фонаря запрещено. Для каждого человека известно время, за которое он пересекает мост. Если по мосту двигаются двое, то время их передвижения равно времени более медленного.

Необходимо вывести минимальное время, за которое все n людей перейдут на другой берег реки, а также последовательность переходов, как указано в примере.

 

Вход. Первая строка содержит количество тестов, за которой следует пустая строка. Тесты разделены друг от друга пустой строкой. Первая строка каждого теста содержит количество людей n (n £ 1000). Следующие n строк содержат время переходов людей через мост. Время перехода каждого человека через мост не более 100 секунд.

 

Выход. Первая строка содержит минимальное время, за которое могут пересечь мост n людей. Далее следует стратегия пересечения моста людьми. Каждая строка стратегии содержит одно или два числа, характеризующие людей, которые с фонарем пересекают мост. При существовании нескольких оптимальных стратегий пересечения реки вывести любую.

 

Пример входа

1

 

4

1

2

5

10

 

Пример выхода

17

1 2

1

5 10

2

1 2

 

 

РЕШЕНИЕ

сортировка

 

Анализ алгоритма

Отсортируем время, за которое люди пересекают реку, по возрастанию. Обозначим через mi время пересечения реки i – ым человеком (m1 £ m2 £ … £ mn).  Рассмотрим, как следует пересекать мост одному, двум или трем людям. При n = 1 и n = 2 оптимальная скорость пересечения реки соответственно равна m1 и m2 = max(m1, m2). При наличии трех людей (n = 3) первый и второй перебираются на другую сторону, самый быстрый (первый) возвращается с фонарем назад и переводит третьего. Таким образом, оптимальное время перехода равно m1 + m2 + m3.

Рассмотрим случай, когда n > 3. Пусть A, B, …, Y, Z – люди, отсортированные по возрастанию времени пересечения моста (A – самый быстрый, Z – самый медленный). Пусть J – это человек, с которым перемещается Z. Если J остается на другом берегу и никогда больше не пойдет по мосту, то оптимально выбрать его равным Y.  Если J будет возвращаться, то его оптимально выбрать самым быстрым, то есть А. Таким образом Z может пересекать мост или с Y, или с А. Вычислим время перевода двух самых медленных людей (Y и Z) согласно этим двум стратегиям.

1. Z идет с Y. Но тогда до этого там должен быть кто-то, кто вернет фонарь, например K. Но этого K также на другой берег должен был кто-то провести чтобы, вернув фонарь, отдать его Y и Z. Пусть им будет L. Таким образом, K и L должны возвращаться. Для минимизации времени в качестве K и L следует выбрать двух самых  быстрых, то есть A и B. Время перевода Y и Z равно mA + 2mB + mZ.

2. Z идет с A, A возвращается. Аналогично A переводит Y и также возвращается. Время перевода Y и Z равно 2mA + mY + mZ.

В обоих случаях через мост переводятся только двое самых медленных людей. Стратегия (первая или вторая) выбирается в зависимости от того, какое из значений (mA + 2mB + mZ или 2mA + mY + mZ) меньше. Если изначально следовало перевести n людей, то далее рекурсивно следует перевести n – 2 людей.

 

Пример

Отсортируем время пересечения моста людьми: 1, 2, 5, 10. Здесь mA = 1, mB = 2, mY = 5, mZ = 10. Время перевода двух самых медленных людей согласно первой и второй стратегиям соответственно равны mA + 2mB + mZ = 1 + 2 * 2 + 10 = 15, 2mA + mY + mZ = 2 * 1 + 5 + 10 = 17. Поскольку первое значение меньше, то следует Z вести с Y. Z с Y переводятся за время 15, после чего остается перевести на другой берег A и B. Это делается за время max{mA, mB} = 2.

 

Реализация алгоритма

В массиве m хранится время перехода людей через реку.

 

Int m[1001];

 

Функция go(n, visible) возвращает оптимальное время, за которое могут пересечь реку n людей. Переменная visible = 1, если следует выводить на экран саму стратегию перехода (visible = 0 иначе).

 

int go(int n,int visible)

{

  int First, Second, Best;

 

Случай пересечения реки одним человеком

 

  if (n == 1)

  {

    if (visible) printf("%d\n",m[0]);

    return m[0];

  } else

 

Случай пересечения реки двумя людьми

 

  if (n == 2)

  {

    if (visible) printf("%d %d\n",m[0],m[1]);

    return m[1];

  } else

 

Случай пересечения реки тремя людьми

 

  if (n == 3)

  {

    if (visible)

    {

      printf("%d %d\n",m[0],m[1]);

      printf("%d\n",m[0]);

      printf("%d %d\n",m[0],m[2]);

    }

    return m[0] + m[1] + m[2];

  };

 

Вычисляем оптимальное время First и Second, которое получается при использовании двух выше описанных стратегий.

 

  First = m[0] + 2 * m[1] + m[n-1];

  Second = 2 * m[0] + m[n-2] + m[n-1];

  Best = (First < Second) ? First : Second;

  if (visible)

  {

    if (Best == First)

    {

      printf("%d %d\n",m[0],m[1]);

      printf("%d\n",m[0]);

      printf("%d %d\n",m[n-2],m[n-1]);

      printf("%d\n",m[1]);

    } else

    {

      printf("%d %d\n",m[0],m[n-2]);

      printf("%d\n",m[0]);

      printf("%d %d\n",m[0],m[n-1]);

      printf("%d\n",m[0]);

    }

  }

 

Рекурсивно вычисляем оптимальную стратегию для оставшихся n – 2 людей.

 

  return Best + go(n-2,visible); 

}

 

Основная часть программы. Читаем количество тестов, вводим время, за которое люди пересекают мост в массив m.

 

  scanf("%d",&tests);

  while(tests--)

  {

    scanf("%d",&n);

    for(i = 0; i < n; i++) scanf("%d",&m[i]);

 

Сортируем время пересечения реки людьми по возрастанию. Запускаем функцию go с параметром visible = 0, которая возвращает оптимальное время пересечения реки. Выводим его, после чего снова запускаем функцию go с параметром visible = 1, которая печатает последовательность переходов. Если текущий тест не последний, то выводим пустую строку.

 

    sort(m,m+n);

    res = go(n,0);

    printf("%d\n",res);

    res = go(n,1);

    if (tests) printf("\n");

  }